#include <iostream>
#include "linearList.h"
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}


//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }


        curNode = curNode->next;
    }
}

sequenceList::sequenceList(const int& maxSize, const int& lenth, float i[])
{
    if (maxSize <= 0 || lenth <= 0) {
        //cout << "非法参数" << endl;
        exit(1);
    }
    if (lenth > maxSize) {
        //cout << "错误,初始化顺序表长度超过最大容量" << endl;
        exit(1);
    }
    if (i == NULL) {
        //cout << "错误,初始化顺序表数组为空" << endl;
        exit(1);
    }
    myList = (float*)malloc(sizeof(float) * maxSize);
    for (int j = 0; j < lenth; j++)
    {
        myList[j] = i[j];
    }
    curNumberOfItem = lenth;
    maxCapcity = maxSize;
}

sequenceList::~sequenceList()
{
    free(myList);
    myList = NULL;
}

bool sequenceList::addItem(const float& item)
{
    if (curNumberOfItem == maxCapcity) {
        return false;
    }
    else {
        myList[curNumberOfItem] = item;
        curNumberOfItem++;
        return true;
    }
}

bool sequenceList::insertItem(const int& p, const float& item)
{
    if (p < 0 || p > curNumberOfItem)
    {
        return false;
    }
    if (curNumberOfItem == maxCapcity)
    {
        return false;
    }
    else
    {
        for (int i = curNumberOfItem - 1; i >= p; i--)
        {
            myList[i + 1] = myList[i];
        }
        myList[p] = item;
        curNumberOfItem++;
        return true;
    }
}

int sequenceList::deleteItem(const float& item)
{
    int i = 0;
    for (; i < curNumberOfItem; i++)
    {
        if (myList[i] == item)
        {
            for (int j = i; j < curNumberOfItem - 1; j++)
            {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    if (i == curNumberOfItem)
    {
        return -1;
    }
}

bool sequenceList::locate(const int& p, float& val)
{
    if (p < 0 || p >= curNumberOfItem)
    {
        return false;
    }
    else
    {
        val = myList[p];
        cout << val << endl;
        return true;
    }
}

int sequenceList::locate(const float& item)
{
    int i = 0;
    for (; i < curNumberOfItem; i++)
    {
        if (myList[i] == item)
        {
            cout << item << i << endl;
            return i;
        }
    }
    if (i == curNumberOfItem)
    {
        return -1;
    }
}

void sequenceList::reverse()
{
    for (int i = 0; i < curNumberOfItem / 2; i++)
    {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - i - 1];
        myList[curNumberOfItem - i - 1] = temp;
    }
}


linkList::linkList(const int& size, float i[])
{
    if (size < 0) {
        cout << "非法参数" << endl;
        exit(1);
    }
    if (size == 0)
    {
        firstNode = NULL;
        lastNode = NULL;
        curNode = NULL;
        listSize = 0;
    }
    listSize = size;
    listNode* Nodes = (listNode*)malloc(sizeof(listNode) * (listSize));
    for (int j = 0; j < size; j++)
    {
        Nodes[j].data = i[j];
    }
    for (int j = 1; j < size; j++)
    {
        Nodes[j - 1].next = &Nodes[j];
    }
    firstNode = (listNode*)malloc(sizeof(listNode));
    lastNode = (listNode*)malloc(sizeof(listNode));
    firstNode->next = &Nodes[0];
    lastNode = &Nodes[size - 1];
}

//需要遍历结点,因为链表每个结点都是独立分配的内存块。
linkList::~linkList()
{
    listNode* temp = (listNode*)malloc(sizeof(listNode));
    while (firstNode->next != NULL)
    {
        temp = firstNode->next;
        free(firstNode->next);
        firstNode = temp->next;
    }
}

//头插法 头节点后插入元素
bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new listNode(item);
    newNode->next = firstNode->next;
    firstNode->next = newNode; //在firstNode节点后插入链表的第一个节点
    if (listSize == 0) lastNode = newNode;//链表从空表变成有元素表
    listSize++;
    return true;
}

//尾插法 
bool linkList::tailInsertItem(const float& item) {
    if (listSize == 0) {
        lastNode = new listNode(item);
    }
    else {
        listNode* newNode = new listNode(item);
        lastNode->next = newNode;
        lastNode = newNode;
    }
    listSize++;
    return true;
}

//插入元素
int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) {
        std::cout << "插入位置错误" << std::endl;
        return -1;
    }
    else if (index == 0) {
        headInsertItem(item);//头插法
        return 0;
    }
    else if (index == listSize) {
        tailInsertItem(item);//尾插法
        return listSize - 1;
    }
    else {
        listNode* temp = firstNode->next;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->next;//遍历到插入位置前节点
        }
        listNode* newNode = new listNode(item);
        newNode->next = temp->next;
        temp->next = newNode;//插入
        listSize++;
        return index;
    }
}

//删除元素
int linkList::deleteItem(const float& item) {
    listNode* temp = (listNode*)malloc(sizeof(listNode));
    temp = firstNode->next;
    listNode* prior = (listNode*)malloc(sizeof(listNode));
    prior = firstNode;
    int i = 0;
    for (; i < listSize; i++) {
        if (temp->data == item) break;
        temp = temp->next;
        prior = prior->next;
    }
    if (i == listSize)  return -1;
    else if (i == listSize - 1) {
        prior->next = NULL;
        lastNode = prior;
        listSize--;
        return i;
    }
    else {
        prior->next = temp->next;
        listSize--;
        return i;
    }
}




//查找元素（按序号找）
bool linkList::locate(const int& p, float& val) {
    if (p < 0 || p >= listSize) {
        return false;//非法位置
    }
    else {
        listNode* temp = firstNode->next;
        for (int i = 0; i < p; i++) {
            temp = temp->next;//按序号查找到元素
        }
        val = temp->data;//存值
        return true;
    }
}

//查找元素（按值找）
int linkList::locate(const float& item) {
    listNode* temp = firstNode->next;
    int i = 0;
    for (; temp != nullptr; i++) {
        if (temp->data == item) {
            return i;
        }
        temp = temp->next;
    }
    return -1;
}


//递增排序
void linkList::ascendingOrder() {
    if (listSize == 0)
    {
        cout << "空链表无法排序" << endl;
        return;
    }
    listNode* current = firstNode->next;
    for (int i = 0; i < listSize - 1; i++)
    {
        for (int j = i + 1; j < listSize; j++)
        {
            if (current->data > current->next->data)
            {
                float tempData = current->data;
                current->data = current->next->data;
                current->next->data = tempData;//使顺序变成增序
            }
            current = current->next;
        }
        current = firstNode->next;//初始化重新开始
    }
}

void linkList::reverse()
{
    if (listSize == 0)
    {
        cout << "空链表无法翻转" << endl;
        return;
    }
    listNode* temp = (listNode*)malloc(sizeof(listNode));
    temp = firstNode->next;
    float datas[listSize];
    for (int i = 0; i < listSize; i++)
    {
        datas[i] = temp->data;
        temp = temp->next;
    }
    for (int i = 0; i < listSize / 2; i++)
    {
        float tempData = datas[i];
        datas[i] = datas[listSize - i - 1];
        datas[listSize - i - 1] = tempData;
    }
    temp = firstNode->next;
    for (int i = 0; i < listSize; i++)
    {
        temp->data = datas[i];
        temp = temp->next;
    }
}

listNode* linkList::getfirstNode()
{
    return firstNode->next;
}
listNode* linkList::getlastNode()
{
    return lastNode;
}
void linkList::increaseCapacity(const int& size)
{
    listSize += size;
    //把原链表的lastNode指针指向新的lastNode
    while (lastNode->next != NULL)
    {
        lastNode = lastNode->next;
    }
}
int linkList::getlistSize()
{
    return listSize;
}

void merge(linkList& A, linkList& B)
{
    A.getlastNode()->next = B.getfirstNode();
    A.increaseCapacity(B.getlistSize());
    A.ascendingOrder();
    A.reverse();
}